//
// Description: 5802. 统计好数字的数目
// Created by Loading on 2021/7/4.
//

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

const int MOD = 1e9 + 7;

/* 快速幂运算 */
uLL fast_power(long long x, long long index) {
    uLL res = 1, base = x;
    /* 将 index 指数转为二进制，遍历二进制序列，为 1 的时候对结果进行累乘 */
    /* 时间复杂度 O(log index)，一般幂运算为 O(index) */
    /* 示例：2^11 ，11 的二进制形式为 1011，结果为：2^8 * 2^3 * 2^0 */
    while (index) {
        if (index & 0x01) {
            res *= base;
            res %= MOD;
        }
        base *= base;
        base %= MOD;
        index >>= 1;
    }
    
    return res;
}

int countGoodNumbers(long long n) {
    uLL res = 1;
    long long prime_num = n / 2;
    long long even_num = n - prime_num;

    //快速幂运算计算 质数的所有情况
    res *= fast_power(4, prime_num);
    res %= MOD;
    //快速幂运算计算 偶数的所有情况
    res *= fast_power(5, even_num);
    res %= MOD;

    return res;
}

int main() {
    cout << countGoodNumbers(100000000) << endl;
}